<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <script>

    //  请你设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构 LRUCache（int
    //   capacity）以正整数作为容器 capacity初始化LRU缓存 int get（int key）如果关键字key存在缓存中，则返回关键字的值，否则返回-1 
    // void put（int key， int value） 如果关键字key已经存在，则变更其数据值的value；如果不存在，则向缓存中插入该组key， value
    // 如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字 函数get和put 必须以0（1）的平均时间复杂度运行


    //  思路
    // 使用双向链表维护缓存项的访问顺序，最近访问的节点放在链表尾部，最久未使用的节点放在链表头部。
    // 使用哈希表快速定位缓存项在链表中的位置，使得查询操作的时间复杂度为 O (1)。
    // 当访问或添加一个缓存项时，将其移动到链表尾部，表示它是最近使用的。
    // 当缓存容量满时，删除链表头部的节点（即最久未使用的节点）。

    // 为什么需要双向链表
    // 双向链表可直接通过prev指针找到前驱节点，删除操作时间复杂度o1
    // 双向链表节点类
    class Node {
      constructor(key, value) {
        this.key = key; // |缓存的键，用来向哈希表中删除
        this.value = value; // 缓存的值
        this.prev = null; // 指向前驱节点的指针
        this.next = null; //指向后续节点的指针
      }
    }

    // 这样写的时间复杂度为o1，空间复杂度是o(capacity)(哈希表和链表最多存储capacity个节点)
    class LRUCache {
      constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();

        // 创建双向链表的头尾节点,方便操作
        // 创建的head 和tail只是一个虚拟节点用于简化边界操作初始状态链表的结构就是
        // head <=> tail
        // 为了删除链表中唯一的实际节点后，链表仍保持head <=> tail 的结构避免了复杂 的空指针判断
        this.head = new Node(null, null);
        this.tail = new Node(null, null);
        this.head.next = this.tail; // 头部最久未使用的节点
        this.tail.prev = this.head; // 最近使用的节点
      }

      // 获取缓存的值
      get(key) {
        // 这里是为了确保被访问的节点始终在链表尾部
        // 如果关键字key存在缓存中，则返回关键字的值，否则返回-1
        // 如果key存在从哈希表获取节点
        if (this.cache.has(key)) {
          const node = this.cache.get(key);
          // 将节点从链表中移除，在添加到尾部（表示最近使用）
          this._remove(node); // 从链表中移除
          this._add(node); // 添加到链表尾部（最近使用）
          // 返回节点值
          return node.value;
        }

        return -1;
      }
      // 为了新插入、更新的节点始终在尾部，容量满时淘汰头部节点
      put(key, value) {
        if (this.cache.has(key)) {
          this._remove(this.cache.get(key)); //如果这个可以已经存在，先删除
        }
        // 创建新节点存入哈希表，并添加到链表尾部
        const node = new Node(key, value);
        this.cache.set(key, node);
        this._add(node); // 添加到链表尾部，最近使用

        // 如果超出容量，删除最久未使用的节点(头部的下一个节点)
        if (this.cache.size > this.capacity) {
          const lruNode = this.head.next;
          this._remove(lruNode);
          this.cache.delete(lruNode.key);
        }
      }
      // 辅助方法从链表中移除节点
      _remove(node) {
        node.prev.next = node.next; // 前驱节点的后继指向当前节点的后继
        node.next.prev = node.prev; // 后继节点的前驱指向当前节点的前驱

        // 帮助理解原操作链表 ...<=>a<=>node<=>B...
        // a.next = B
        // b.prev = a
      }

      // 辅助方法，添加节点到链表尾部

      _add(node) {
        node.prev = this.tail.prev; // 新节点的前驱指向原尾节点的前驱
        node.next = this.tail; //新节点的后继指向尾节点
        this.tail.prev.next = node; // 原尾节点的前驱的后继指向新节点
        this.tail.prev = node; // 尾节点的前驱指向新节点

        // 可以这样理解 原来链表 ...<=> A <=> tail
        // node.prev = A
        // node.next = tail
        // A.next = node
        // tail.prev = node
      }
    }
  </script>
  <body>
    <div>
     
    </div>
  </body>
</html>
